package BinaryTree;

//二叉树的最大宽度: https://leetcode.cn/problems/maximum-width-of-binary-tree/description/
//时间复杂度: O(n)
public class Code4 {
	public static int MAXN=3001;
	
	public static TreeNode[] queue=new TreeNode[MAXN];  //存储节点
	
	public static int[] pos=new int[MAXN];              //存储节点对应的编号
	
	public static int l,r;
	public int widthOfBinaryTree(TreeNode root) {
		int ret=0;
		if(root!=null) {
			l=r=0;            //必须有这条语句。否则有脏数据
			queue[r]=root;
			pos[r++]=1;
			while(l<r) {
				int size=r-l;
				//  左............右
				//  l ............r-1  => pos[r-1]-pos[l]+1=第i层的节点数
				ret=Math.max(ret,pos[r-1]-pos[l]+1);  
				
				for(int i=0;i<size;i++) {
					
					TreeNode cur=queue[l];
					int index=pos[l++];
	
					if(cur.left!=null) {   //左孩子入数组
						queue[r]=cur.left;
						pos[r++]=index*2;
					}
					if(cur.right!=null) {  //右孩子入数组
						queue[r]=cur.right;
						pos[r++]=index*2+1;
					}
				}
			}
		}
        return ret;
    }
}
